package questionSolution.Question_15;
import java.util.*;
/*
排序的作用
排序是双指针解法的基础，能将数组元素按大小排列，便于通过移动指针调整三数之和
排序后相同元素相邻，为去重提供了便利
双指针技巧：
固定一个元素（nums[i]）后，用左右指针（left=i+1,right=n-1）在剩余区间寻找另外两个元素，使三数之和为0.
通过比较当前的目标值（0）的大小，移动指针
和小于0：右移左指针
和大于0：左移右指针
和等于0：记录三元组

 */
public class Solution_1 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++){
            int left = i + 1;
            int right = nums.length - 1;
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            while (left < right){
                int temp = nums[left] + nums[right] + nums[i];
                if (temp == 0){
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    right--;
                    while (left < right && nums[right] == nums[right+1]){
                        right--;
                    }
                    continue;
                }
                else if(temp < 0){
                    left++;
                    continue;
                }
                else{
                    right--;
                    continue;
                }
            }
        }
        return res;
    }

    static void main() {
        Solution_1 s = new Solution_1();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        List<List<Integer>> res = s.threeSum(nums);
        System.out.println(res);
    }
}
